package com.sx.sx1.lintcode.day717;

import java.util.Stack;

public class LC1746 {

      static class TreeNode {
      public int val;
      public TreeNode left, right;
      public TreeNode(int val) {
          this.val = val;
          this.left = this.right = null;
      }
  }


    static class Solution {
        /**
         * @param root:  a Binary Search Tree (BST) with the root node
         * @return: the minimum difference
         */
        public int minDiffInBST(TreeNode root) {
            Integer ans =null;
            Stack<TreeNode> s = new Stack<>();
            TreeNode pre =null;
            TreeNode previosnode = null;
            while (!s.isEmpty() || root!=null){
                while (root!=null){
                    s.add(root);
                    root = root.left;
                }

                root= s.peek();

                if(previosnode ==null){
                    previosnode = root;
                }else{
                    int diff = root.val- previosnode.val;
                    if(diff<0) diff*=-1;
                    if(ans ==null) ans =diff;
                    else if(ans> diff) ans=diff;
                }


                if(root.right ==null || root.right==pre){
                    root = s.pop();
                    pre = root;
                    root =null;
                }else{
                    root = root.right;
                }
            }

            return ans;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有216条未读消息，请及时查看
1746 · 二叉搜索树结点最小距离
算法
简单
通过率
55%

题目
题解23
笔记
讨论17
排名
记录
描述
给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


二叉树的大小范围在 2 到 100。
二叉树总是有效的，每个节点的值都是整数，且不重复。
样例
样例 1:

输入: root = {4,2,6,1,3}
输出: 1
解释:
注意，root是树结点对象(TreeNode object)，而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

          4
        /   \
      2      6
     / \
    1   3

最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
样例 2:

输入: root = {2,1}
输出: 1
解释:
注意，root是树结点对象(TreeNode object)，而不是数组。

给定的树 {2,1} 可表示为下图:

      2
     /
    1

最小的差值是 1, 它是节点1和节点2的差值。
标签
企业
Amazon
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
301/1859
已开启智能提示
发起考试
15 分 00 秒
123456789101112131415161718192021


public class Solution {
    /**
     * @param root:  a Binary Search Tree (BST) with the root node
     * @return: the minimum difference

    public int minDiffInBST(TreeNode root) {
        // Write your code here.
    }

    控制台
            历史提交

 */
